package kyssion.leetcode.num101_150;

public class code134_加油站 {
    public static void main(String[] args) {
        System.out.println(new code134_加油站().canCompleteCircuit(
                new int[]{
                        5, 5, 1, 3, 4}, new int[]{
                        8, 1, 7, 1, 1}
        ));
    }

    /**
     * 简单暴力求解的过程中我们发现如果车子跑到k的时候没油了
     * 那么说明从i 到 k 都会没油的
     * 如果跑到了列表的最后,那就说明起点就是 i
     * @param gas
     * @param cost
     * @return
     */
    int canCompleteCircuit(int[] gas, int[] cost) {
        int rest = 0, run = 0, start = 0;
        for (int i = 0; i < gas.length; ++i) {
            run += (gas[i] - cost[i]);
            rest += (gas[i] - cost[i]);
            if (run < 0) {
                start = i + 1;
                run = 0;
            }
        }
        return rest < 0 ? -1 : start;
    }
}
